PE424001 Algorithm and Data Structure
Assignment 1
(25% of the module score)
Q1. (10 Marks) With an infix expression in the form of :
((A-B)+C*(D+E))-(F+G)
a) What is the prefix expression? Illustrates your steps using a Stack data structure. (4 Marks)
b) Verify your result by assigning the values to variables and shows your steps. (4 Marks)
A=7 , B=6, C=5, D=4, E=3, F=2, G=1
c) What is the final answer in b)? (1 Mark)
d) Give one example in which Stack is always used. (1 Mark)
Q2. (10 Marks) Given an input array
[ 5 2 6 1 7 9 4 3]
a) Trace the action of:
1 Selection Sort (1 Mark)
2 Insertion Sort (1 Mark)
b) Refer to the following number list which is sorted by bubble sort and in ascending order. (5 Marks)
Initial list: 18, 17, 13, 26, 10, 14, 24
After 1st pass: 17 13 18 10 14 24 26
After 2nd pass: 13 17 10 14 18 24 26
After 3rd pass: 13 10 14 17 18 24 26
After 4th pass: 10 13 14 17 18 24 26
After 5th pass: 10 13 14 17 18 24 26
What is the number of comparisons and swaps in each pass? Specify your answer in each pass.
c) What is the maximum number of comparisons and the maximum number of swaps that might be needed in b) if the sequence is in descending order. (2 Marks)
d) Compare the below sorting algorithms worst performance in terms of Big-O ( All correct, 1 Mark)
QuickSort
Selection Sort
Insertion Sort
Q3. (5 Marks)
a) Write down the number sequence with the following order traversal by referencing the following tree.
(1) preorder
(2) inorder
(3) postorder (0.5 each, 1.5 Marks)
b) Construct a Binary Search Tree (BST) by inserting the following keys (from left to right): The tree initially is empty. key ={17, 9, 26, 12, 11, 7, 30, 20, 21, 10} (2.5 Marks)
c) By using the BST from question Q3b, draw the BST after the key 17 is deleted (1 Marks)
iii) Submission
– DEADLINE: 22:00:00 21st August, 2015
– Submission method:
1. Zip up all the files and name the zip file to “[Last name]_[First name].zip”. (E.g. Chan_Peter.zip)
2. Send the zip file to alexng88@vtc.edu.hk
3. Enter “ADS Assignment 1 Submission – [Last name] [First name]” in the subject.
4. Marks will be deducted if you don’t follow the submission method.
Marks will be deducted on late submission.
iv) Marking Scheme
This assignment contributes 25% of the final grade of PE424001
The full mark for this assignment is 25 marks, which break down into:
– Question 1 & 2 contributes 10 marks each.
-Question 3 contributes 5 marks.
– End –
1 week
Your marks x 90%
2 weeks
Your marks x 80%
More than 2 weeks
Your marks x 0%

PE424001 Algorithm and Data Structure
Assignment 1
(25% of the module score)
Q1. (10 Marks) With an infix expression in the form of :
((A-B)+C*(D+E))-(F+G)
a) What is the prefix expression? Illustrates your steps using a Stack data structure. (4 Marks)
b) Verify your result by assigning the values to variables and shows your steps. (4 Marks)
A=7 , B=6, C=5, D=4, E=3, F=2, G=1
c) What is the final answer in b)? (1 Mark)
d) Give one example in which Stack is always used. (1 Mark)
Q2. (10 Marks) Given an input array
[ 5 2 6 1 7 9 4 3]
a) Trace the action of:
1 Selection Sort (1 Mark)
2 Insertion Sort (1 Mark)
b) Refer to the following number list which is sorted by bubble sort and in ascending order. (5 Marks)
Initial list: 18, 17, 13, 26, 10, 14, 24
After 1st pass: 17 13 18 10 14 24 26
After 2nd pass: 13 17 10 14 18 24 26
After 3rd pass: 13 10 14 17 18 24 26
After 4th pass: 10 13 14 17 18 24 26
After 5th pass: 10 13 14 17 18 24 26
What is the number of comparisons and swaps in each pass? Specify your answer in each pass.
c) What is the maximum number of comparisons and the maximum number of swaps that might be needed in b) if the sequence is in descending order. (2 Marks)
d) Compare the below sorting algorithms worst performance in terms of Big-O ( All correct, 1 Mark)
QuickSort
Selection Sort
Insertion Sort
Q3. (5 Marks)
a) Write down the number sequence with the following order traversal by referencing the following tree.
(1) preorder
(2) inorder
(3) postorder (0.5 each, 1.5 Marks)
b) Construct a Binary Search Tree (BST) by inserting the following keys (from left to right): The tree initially is empty. key ={17, 9, 26, 12, 11, 7, 30, 20, 21, 10} (2.5 Marks)
c) By using the BST from question Q3b, draw the BST after the key 17 is deleted (1 Marks)
iii) Submission
– DEADLINE: 22:00:00 21st August, 2015
– Submission method:
1. Zip up all the files and name the zip file to “[Last name]_[First name].zip”. (E.g. Chan_Peter.zip)
2. Send the zip file to alexng88@vtc.edu.hk
3. Enter “ADS Assignment 1 Submission – [Last name] [First name]” in the subject.
4. Marks will be deducted if you don’t follow the submission method.
Marks will be deducted on late submission.
iv) Marking Scheme
This assignment contributes 25% of the final grade of PE424001
The full mark for this assignment is 25 marks, which break down into:
– Question 1 & 2 contributes 10 marks each.
-Question 3 contributes 5 marks.
– End –
1 week
Your marks x 90%
2 weeks
Your marks x 80%
More than 2 weeks
Your marks x 0%

PE424001 Algorithm and Data Structure
Assignment 1
(25% of the module score)
Q1. (10 Marks) With an infix expression in the form of :
((A-B)+C*(D+E))-(F+G)
a) What is the prefix expression? Illustrates your steps using a Stack data structure. (4 Marks)
b) Verify your result by assigning the values to variables and shows your steps. (4 Marks)
A=7 , B=6, C=5, D=4, E=3, F=2, G=1
c) What is the final answer in b)? (1 Mark)
d) Give one example in which Stack is always used. (1 Mark)
Q2. (10 Marks) Given an input array
[ 5 2 6 1 7 9 4 3]
a) Trace the action of:
1 Selection Sort (1 Mark)
2 Insertion Sort (1 Mark)
b) Refer to the following number list which is sorted by bubble sort and in ascending order. (5 Marks)
Initial list: 18, 17, 13, 26, 10, 14, 24
After 1st pass: 17 13 18 10 14 24 26
After 2nd pass: 13 17 10 14 18 24 26
After 3rd pass: 13 10 14 17 18 24 26
After 4th pass: 10 13 14 17 18 24 26
After 5th pass: 10 13 14 17 18 24 26
What is the number of comparisons and swaps in each pass? Specify your answer in each pass.
c) What is the maximum number of comparisons and the maximum number of swaps that might be needed in b) if the sequence is in descending order. (2 Marks)
d) Compare the below sorting algorithms worst performance in terms of Big-O ( All correct, 1 Mark)
QuickSort
Selection Sort
Insertion Sort
Q3. (5 Marks)
a) Write down the number sequence with the following order traversal by referencing the following tree.
(1) preorder
(2) inorder
(3) postorder (0.5 each, 1.5 Marks)
b) Construct a Binary Search Tree (BST) by inserting the following keys (from left to right): The tree initially is empty. key ={17, 9, 26, 12, 11, 7, 30, 20, 21, 10} (2.5 Marks)
c) By using the BST from question Q3b, draw the BST after the key 17 is deleted (1 Marks)
iii) Submission
– DEADLINE: 22:00:00 21st August, 2015
– Submission method:
1. Zip up all the files and name the zip file to “[Last name]_[First name].zip”. (E.g. Chan_Peter.zip)
2. Send the zip file to alexng88@vtc.edu.hk
3. Enter “ADS Assignment 1 Submission – [Last name] [First name]” in the subject.
4. Marks will be deducted if you don’t follow the submission method.
Marks will be deducted on late submission.
iv) Marking Scheme
This assignment contributes 25% of the final grade of PE424001
The full mark for this assignment is 25 marks, which break down into:
– Question 1 & 2 contributes 10 marks each.
-Question 3 contributes 5 marks.
– End –
1 week
Your marks x 90%
2 weeks
Your marks x 80%
More than 2 weeks
Your marks x 0%